Data processing systems using convolutional codes are theoretically capable of reaching the Shannon limit, a theoretical limit of signal-to-noise for error-free communications. Prior to the discovery of turbo codes in 1993, convolutional codes were decoded with Viterbi decoders. However, as error correction requirements increased, the complexity of Viterbi decoders exponentially increased. Consequently, a practical limit on systems employing Viterbi decoders to decode convolutional codes was about 3 to 6 dB from the Shannon limit. The introduction of turbo codes allowed the design of practical decoders capable of achieving a performance about 0.7 dB from the Shannon limit, surpassing the performance of convolutional-encoder/Viterbi-decoders of similar complexity. Therefore, turbo codes offered significant advantage over prior code techniques.
Convolutional codes are generated by interleaving data. There are two types of turbo code systems: ones that use parallel concatenated convolutional codes, and ones that use serially concatenated convolutional codes. Data processing systems that employ parallel concatenated convolutional codes decode the codes in several stages. In a first stage, the original data (e.g. sequence of symbols) are processed, and in a second stage the data obtained by permuting the original sequence of symbols is processed, usually using the same process as in the first stage. The data are processed in parallel, requiring that the data be stored in several memories and accessed in parallel for the respective stage. However, parallel processing often causes conflicts. More particularly, two or more elements or sets of data that are required to be accessed in a given cycle may be in the same memory, and therefore not accessible in parallel. Consequently, the problem becomes one of organizing access to the data so that all required data can simultaneously accessed in each of the processing stages.
Traditionally, turbo decoding applications increased throughput by adding additional parallel turbo decoders. However, in integrated circuit (IC) designs, the additional decoders were embodied on the IC and necessarily increased chip area dramatically. There is a need for a turbo decoder that achieves high throughput without duplication of parallel turbo decoders, thereby achieving reduced IC chip area.